LeetCode 67、二进制求和

一、题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二进制求和（LeetCode 67）：https://leetcode.cn/problems/add-binary/
class Solution {
    public String addBinary(String a, String b) {

        // 使用字符串去拼接每一次计算的结果
        StringBuilder ans = new StringBuilder();

        // 二进制计算过程中产生的进位
        int carry = 0;

        // 开始计算
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            
            // 获取字符串 a 中对应的字符，如果有，那就是 a.charAt(i) - '0' 这个数字，否则设置为 0
            int numA = i >= 0 ? a.charAt(i) - '0' : 0;

            // 获取字符串 b 中对应的字符，如果有，那就是 b.charAt(i) - '0' 这个数字，否则设置为 0
            int numB = j >= 0 ? b.charAt(j) - '0' : 0;

            // 每次计算的过程都是 字符串 a 对应的字符 + 字符串 b 对应的字符 + 前面产生的进位
            // 这里采取的是【十进制】的计算规则，比如 1 + 1 = 2
            int sum = numA + numB + carry;
            
            // 需要把 sum 拆解为二进制的形式，比如十进制的结果 2 为二进制的 10
            // 通过 %2 的操作，可以把 0 存储到 ans 中
            ans.append(sum % 2);

            // 通过 /2 的操作，可以把 1 存储到 carry 中
            carry = sum / 2;

        }

        // 最后，需要观察最后的计算过程中是否还有进位没有使用到
        ans.append(carry == 1 ? carry : "");

        // 由于整个计算过程是从后向前计算，导致低位的计算结果存储在 ans 的前面
        // 所以需要翻转一下
        return ans.reverse().toString();
    }
}

2、C++ 代码

class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0;
        string res = "";
        for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; i--, j--)
        {
            int sum = carry;
            sum += i >= 0 ? a[i] - '0' : 0;
            sum += j >= 0 ? b[j] - '0' : 0;
            res += (sum % 2) + '0';
            carry = sum / 2;
        }
        if (carry == 1) res += '1';
        reverse(res.begin(), res.end());
        return res;
        
    }
};

3、Python 代码

class Solution(object):
    def addBinary(self, a, b):
        res = ""
        carry = 0
        i = len(a) - 1
        j = len(b) - 1
        while i >= 0 or j >= 0 or carry != 0:
            digitA = int(a[i]) if i >= 0 else 0
            digitB = int(b[j]) if j >= 0 else 0
            sum = digitA + digitB + carry
            carry = 1 if sum >= 2 else 0
            sum = sum - 2 if sum >= 2 else sum
            res += str(sum)
            i -= 1
            j -= 1
        return res[::-1]